// https://leetcode.cn/problems/longest-turbulent-subarray/

// 算法思路总结：
// 1. 使用双状态动态规划处理湍流数组问题
// 2. f[i]表示以i结尾且arr[i] > arr[i-1]的最大长度
// 3. g[i]表示以i结尾且arr[i] < arr[i-1]的最大长度
// 4. 根据相邻元素大小关系进行状态转移
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int maxTurbulenceSize(vector<int>& arr) 
    {
        int m = arr.size();
        if (m == 1) return 1;

        vector<int> f(m, 1), g(m, 1);
        int ret = 0;
        for (int i = 1 ; i < m ; i++)
        {
            if (arr[i] > arr[i - 1])
                f[i] = g[i - 1] + 1;
            else if (arr[i] < arr[i - 1])
                g[i] = f[i - 1] + 1;
            ret = max({ret, f[i], g[i]});
        }
        return ret;
    }
};

int main()
{
    vector<int> v1 = {9,4,2,10,7,8,8,1,9}, v2 = {4,8,12,16};
    Solution sol;

    cout << sol.maxTurbulenceSize(v1) << endl;
    cout << sol.maxTurbulenceSize(v2) << endl;

    return 0;
}